package 代码随想录_回溯.力扣_回溯.岛屿系列;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author zx
 * @create 2022-08-12 22:21
 * https://leetcode.cn/problems/making-a-large-island/solution/dao-yu-wen-ti-mei-you-na-yao-nan-du-li-x-cgbv/
 */
public class 最大人工岛_827 {
    /**
     * @return
     * 总体思路： 对网格做两遍 DFS：第一遍 DFS 遍历陆地格子, 计算每个岛屿的面积并标记岛屿
     * 第二遍 DFS 遍历海洋格子,观察每个海洋格子相邻的岛屿格子。重点！！！把每个岛屿格子的值标为面积
     */
    public int largestIsland(int[][] grid) {
        int index = 2; // 岛屿编号,//0是海洋1是陆地,为了避免冲突,从2开始
        //序号对应面积的一个映射，因为面积要最后结束才能计算出来，所以遍历过程中用index代替，放在映射中
        Map<Integer, Integer> map = new HashMap<>(); //岛屿编号 -> 岛屿面积的map
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, index);
                    map.put(index, area);
                    index++;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                //依次尝试填海
                int tian = helper(grid, i, j, map);
                res = Math.max(res, tian);
            }
        }

        return res;
    }

    // 把(i, j)填海之后, 最大的岛屿面积

    /**
     * @return 这个方法没有看懂！！！！！！！！！！！
     * 对于海洋格子，找到上下左右
     * 每个方向,都要确保有效inArea以及是陆地格子,则表示是该海洋格子的陆地邻居
     */
    private int helper(int[][] grid, int i, int j, Map<Integer, Integer> map) {
        if (grid[i][j] != 0) {
            return map.get(grid[i][j]);
        }
        int res = 0;
        Set<Integer> set = new HashSet<>();
        if (inArea(grid, i - 1, j) && grid[i - 1][j] > 0) {
            set.add(grid[i - 1][j]);
        }
        if (inArea(grid, i + 1, j) && grid[i + 1][j] > 0) {
            set.add(grid[i + 1][j]);
        }
        if (inArea(grid, i, j - 1) && grid[i][j - 1] > 0) {
            set.add(grid[i][j - 1]);
        }
        if (inArea(grid, i, j + 1) && grid[i][j + 1] > 0) {
            set.add(grid[i][j + 1]);
        }
        for (int adj : set) {
            res += map.get(adj);
        }
        return res + 1;
    }
    // value 表示当前岛屿编号
    private int dfs(int[][] grid, int i, int j, int index) {
        if (!inArea(grid, i, j)) {
            return 0;
        }
        if (grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = index;
        return 1 + dfs(grid, i - 1, j, index)
                 + dfs(grid, i + 1, j, index)
                 + dfs(grid, i, j - 1, index)
                 + dfs(grid, i, j + 1, index);
    }
    private boolean inArea(int[][] grid, int i, int j) {
        return 0 <= i && i < grid.length
                && 0 <= j && j < grid[0].length;
    }
}
